package leetcode_en

import (
	"container/heap"
	"go-study/src/leetcode"
	"go-study/src/utils"
	"math"
	"strconv"
	"strings"
)

/**
 * @Description: 566. Reshape the Matrix
 * @Keyword: python的数据处理中就有这个函数，改变数据的行列
 * @Author: kami
 * @Date: 2021/12/28 21:39
 **/
func matrixReshape(mat [][]int, r int, c int) [][]int {
	row := len(mat)
	col := len(mat[0])
	if row*col != r*c {
		return mat
	}
	var res [][]int
	var cIdx = 0
	var cur []int
	for i := 0; i < row; i++ {
		for j := 0; j < col; j++ {
			if cIdx+1 < c {
				cur = append(cur, mat[i][j])
				cIdx++
			} else {
				cur = append(cur, mat[i][j])
				res = append(res, cur)
				cur = []int{}
				cIdx = 0
			}
		}
	}
	return res
}

/**
 * @Description: 572. Subtree of Another Tree
 * @Keyword: 递归遍历树，递归遍历子树
 * @Author: kami
 * @Date: 2021/12/28 22:42
 **/
func isSubtree(root *leetcode.TreeNode, subRoot *leetcode.TreeNode) bool {
	return dfsTree(root, subRoot)
}

func dfsTree(cur *leetcode.TreeNode, subRoot *leetcode.TreeNode) bool {
	if cur == nil {
		return false
	}
	var curRes bool
	if cur.Val == subRoot.Val {
		curRes = dfsSubTree(cur, subRoot)
	}
	return curRes || dfsTree(cur.Left, subRoot) || dfsTree(cur.Right, subRoot)
}

func dfsSubTree(root *leetcode.TreeNode, subRoot *leetcode.TreeNode) bool {
	if subRoot == nil {
		if root != nil {
			return false
		}
		return true
	}

	if root == nil || root.Val != subRoot.Val {
		return false
	}

	return dfsSubTree(root.Left, subRoot.Left) && dfsSubTree(root.Right, subRoot.Right)
}

/**
 * @Description: 575. Distribute Candies
 * @Keyword: 简单
 * @Author: kami
 * @Date: 2021/12/28 23:14
 **/
func distributeCandies(candyType []int) int {
	n := len(candyType) / 2
	typeMap := make(map[int]bool)
	var cnt = 0
	for i := 0; i < len(candyType); i++ {
		if !typeMap[candyType[i]] {
			typeMap[candyType[i]] = true
			cnt++
		}
		if cnt >= n {
			return cnt
		}
	}
	return cnt
}

/**
 * @Description: 594. Longest Harmonious Subsequence
 * @Keyword:
 * @Author: kami
 * @Date: 2021/12/29 21:40
 **/
func findLHS(nums []int) int {
	// 小的数:小的数和大1的数的个数
	// 1, 3, 2, 2, 5, 2, 3, 7
	minMap := make(map[int]int)
	var max int
	for i := 0; i < len(nums); i++ {
		minMap[nums[i]] += 1
	}

	for key, val := range minMap {
		var nextVal = minMap[key+1]
		if nextVal <= 0 {
			continue
		}
		sum := val + nextVal
		if sum > max {
			max = sum
		}
	}
	return max
}

/**
 * @Description: 598. Range Addition II
 * @Keyword: 计算那个区间的数字被加的次数最多，区间的个数就是结果
 * @Author: kami
 * @Date: 2021/12/30 22:01
 **/
func maxCount(m int, n int, ops [][]int) int {
	if ops == nil || len(ops) == 0 {
		return m * n
	}
	intSize := 32 << (^uint(0) >> 63) // 32 or 64

	MaxInt := 1<<(intSize-1) - 1
	var row, col = MaxInt, MaxInt
	for i := 0; i < len(ops); i++ {
		row = utils.GetMin(row, ops[i][0])
		col = utils.GetMin(col, ops[i][1])
	}
	return row * col
}

/**
 * @Description: 599. Minimum Index Sum of Two Lists
 * @Keyword:
 * @Author: kami
 * @Date: 2022/1/1 21:04
 **/
func findRestaurant(list1 []string, list2 []string) []string {
	existMap := make(map[string]int)
	size1 := len(list1)
	size2 := len(list2)
	var minIndex = size1 + size2
	for i := 0; i < size1; i++ {
		existMap[list1[i]] = i
	}
	var res []string
	minIndex = size1 + size2
	for i := 0; i < size2; i++ {
		if idx, ok := existMap[list2[i]]; ok {
			var sum = idx + i
			if sum < minIndex {
				res = []string{list2[i]}
				minIndex = sum
			} else if sum == minIndex {
				res = append(res, list2[i])
			}
		}
	}
	return res
}

/**
 * @Description: 605. Can Place Flowers
 * @Keyword: 是否能把话放到花床里，间隔着
 * @Author: kami
 * @Date: 2022/1/1 21:25
 **/
func canPlaceFlowers(flowerbed []int, n int) bool {
	var count int
	var size = len(flowerbed)
	var subOneSize = size - 1
	for i := 0; i < size && count < n; i++ {
		if flowerbed[i] != 0 {
			continue
		}
		var next int
		if i != subOneSize {
			next = flowerbed[i+1]
		}
		var prev int
		if i != 0 {
			prev = flowerbed[i-1]
		}
		if next == 0 && prev == 0 {
			flowerbed[i] = 1
			count++
		}
	}
	return count == n
}

/**
 * @Description: 606. Construct String from Binary Tree
 * @Keyword: 递归
 * @Author: kami
 * @Date: 2022/1/2 10:38
 **/
func tree2str(root *leetcode.TreeNode) string {
	if root == nil {
		return ""
	}
	var result = strconv.Itoa(root.Val)
	var left = tree2str(root.Left)
	var right = tree2str(root.Right)
	switch {
	case left == "" && right == "":
		return result
	case left == "":
		return result + "()" + "(" + right + ")"
	case right == "":
		return result + "(" + left + ")"
	default:
		return result + "(" + left + ")" + "(" + right + ")"
	}
}

/**
 * @Description: 628. Maximum Product of Three Numbers
 * @Keyword: 获取大小
 * @Author: kami
 * @Date: 2022/1/2 11:28
 **/
func maximumProduct(nums []int) int {
	var max1, max2, max3, min1, min2 = utils.MinInt, utils.MinInt, utils.MinInt, utils.MaxInt, utils.MaxInt
	for i := 0; i < len(nums); i++ {
		n := nums[i]
		if n > max1 {
			max3 = max2
			max2 = max1
			max1 = n
		} else if n > max2 {
			max3 = max2
			max2 = n
		} else if n > max3 {
			max3 = n
		}
		if n < min1 {
			min2 = min1
			min1 = n
		} else if n < min2 {
			min2 = n
		}
	}
	return utils.GetMax(max1*max2*max3, max1*min1*min2)
}

/**
 * @Description: 637. Average of Levels in Binary Tree
 * @Keyword: 使用队列，按层入队
 * @Author: kami
 * @Date: 2022/1/2 12:06
 **/
func averageOfLevels(root *leetcode.TreeNode) []float64 {
	var arr = []*leetcode.TreeNode{root}
	var res []float64
	for size := len(arr); size > 0; {
		var sum int
		var curLevelArr []*leetcode.TreeNode
		for i := 0; i < size; i++ {
			sum += arr[i].Val
			if arr[i].Left != nil {
				curLevelArr = append(curLevelArr, arr[i].Left)
			}
			if arr[i].Right != nil {
				curLevelArr = append(curLevelArr, arr[i].Right)
			}
		}
		res = append(res, float64(sum)/float64(size))
		arr = curLevelArr
		size = len(arr)
	}
	return res
}

/**
 * @Description: 643. Maximum Average Subarray I
 * @Keyword: [9,7,3,5,6,2,0,8,1,9]
 * @Author: kami
 * @Date: 2022/1/2 12:44
 **/
func findMaxAverage(nums []int, k int) float64 {
	size := len(nums)
	if size == k {
		var sum int
		for i := 0; i < k; i++ {
			sum += nums[i]
		}
		return float64(sum) / float64(k)
	}
	var sumArr []int
	var sum int
	for i := 0; i < k; i++ {
		sum += nums[i]
	}
	sumArr = append(sumArr, sum)
	for i := k; i < size; i++ {
		sum = sum - nums[i-k] + nums[i]
		sumArr = append(sumArr, sum)
	}
	var max = utils.MinInt
	for i := 0; i < len(sumArr); i++ {
		if sumArr[i] > max {
			max = sumArr[i]
		}
	}
	return float64(max) / float64(k)
}

/**
 * @Description: 645. Set Mismatch
 * @Keyword: 数字与下标之间的关系
 * @Author: kami
 * @Date: 2022/1/2 13:11
 **/
func findErrorNums(nums []int) []int {
	var res [2]int
	for _, num := range nums {
		if nums[utils.Abs(num)-1] < 0 {
			res[0] = utils.Abs(num)
		} else {
			nums[utils.Abs(num)-1] *= -1
		}
	}
	for i := range nums {
		if nums[i] > 0 {
			res[1] = i + 1
		}
	}
	return res[0:]

}

/**
 * @Description: 653. Two Sum IV - Input is a BST
 * @Keyword: twosum的变形，是遍历原数据的方式变化
 * @Author: kami
 * @Date: 2022/1/2 13:36
 **/
func findTarget(root *leetcode.TreeNode, k int) bool {
	return dfsTarget(root, map[int]bool{}, k)
}

func dfsTarget(cur *leetcode.TreeNode, seen map[int]bool, target int) bool {
	if cur == nil {
		return false
	}
	if seen[target-cur.Val] {
		return true
	}
	seen[cur.Val] = true
	return dfsTarget(cur.Left, seen, target) || dfsTarget(cur.Right, seen, target)
}

/**
 * @Description: 657. Robot Return to Origin
 * @Keyword: 统计步数
 * @Author: kami
 * @Date: 2022/1/2 13:42
 **/
func judgeCircle(moves string) bool {
	return strings.Count(moves, "U") == strings.Count(moves, "D") &&
		strings.Count(moves, "L") == strings.Count(moves, "R")
}

/**
 * @Description: 661. Image Smoother
 * @Keyword: 平均
 * @Author: kami
 * @Date: 2022/1/2 14:03
 **/
func imageSmoother(img [][]int) [][]int {
	grays := make([][]int, len(img))
	for i, l1 := 0, len(img); i < l1; i++ {
		grays[i] = make([]int, len(img[i]))
	}

	for i, l1 := 0, len(img); i < l1; i++ {
		for j, l2 := 0, len(img[i]); j < l2; j++ {
			sum := img[i][j]
			count := 1

			// up left
			if i > 0 && j > 0 {
				sum += img[i-1][j-1]
				count++
			}

			// up middle
			if i > 0 {
				sum += img[i-1][j]
				count++
			}

			// up right
			if i > 0 && j < l2-1 {
				sum += img[i-1][j+1]
				count++
			}

			// left
			if j > 0 {
				sum += img[i][j-1]
				count++
			}

			// right
			if j < l2-1 {
				sum += img[i][j+1]
				count++
			}

			// down left
			if i < l1-1 && j > 0 {
				sum += img[i+1][j-1]
				count++
			}

			// down middle
			if i < l1-1 {
				sum += img[i+1][j]
				count++
			}

			// down right
			if i < l1-1 && j < l2-1 {
				sum += img[i+1][j+1]
				count++
			}

			grays[i][j] = sum / count
		}
	}
	return grays
}

/**
 * @Description: 671. Second Minimum Node In a Binary Tre
 * @Keyword: 找到老二
 * @Author: kami
 * @Date: 2022/1/3 9:41
 **/
func findSecondMinimumValue(root *leetcode.TreeNode) int {
	if root.Left == nil {
		return -1
	}
	var l, r int
	if root.Left.Val == root.Val {
		l = findSecondMinimumValue(root.Left)
	} else {
		l = root.Left.Val
	}

	if root.Right.Val == root.Val {
		r = findSecondMinimumValue(root.Right)
	} else {
		r = root.Right.Val
	}

	if l == -1 || r == -1 {
		return utils.GetMax(l, r)
	}
	return utils.GetMin(l, r)
}

/**
 * @Description: 674. Longest Continuous Increasing Subsequence
 * @Keyword: 连续升序长度
 * @Author: kami
 * @Date: 2022/1/3 10:39
 **/
func findLengthOfLCIS(nums []int) int {
	var max = 1
	var tempMax = 1
	for i := 1; i < len(nums); i++ {
		if nums[i] > nums[i-1] {
			tempMax++
		} else {
			if tempMax > max {
				max = tempMax
			}
			tempMax = 1
		}
	}
	if tempMax > max {
		return tempMax
	}
	return max
}

/**
 * @Description: 680. Valid Palindrome II
 * @Keyword: 删除一个看是不是回文符串
 * @Author: kami
 * @Date: 2022/1/3 10:48
 **/
func validPalindrome(s string) bool {
	return validPalindromeByDelete(s, false)
}

func validPalindromeByDelete(s string, hasDelete bool) bool {
	size := len(s)
	var left, right = 0, size - 1
	for left < right {
		if s[left] != s[right] {
			if hasDelete {
				return false
			} else {
				return validPalindromeByDelete(s[left:right], true) || validPalindromeByDelete(s[left+1:right+1], true)
			}
		} else {
			left++
			right--
		}
	}
	return true
}

/**
 * @Description: 682. Baseball Game
 * @Keyword: 计分
 * @Author: kami
 * @Date: 2022/1/3 11:02
 **/
func calPoints(ops []string) int {
	var record []int
	for i := 0; i < len(ops); i++ {
		switch ops[i] {
		case "C":
			record = record[:len(record)-1]
		case "D":
			record = append(record, 2*record[len(record)-1])
		case "+":
			tempSize := len(record)
			record = append(record, record[tempSize-1]+record[tempSize-2])
		default:
			val, _ := strconv.ParseInt(ops[i], 10, 0)
			record = append(record, int(val))
		}
	}
	for i := 1; i < len(record); i++ {
		record[0] += record[i]
	}
	return record[0]
}

/**
 * @Description: 693. Binary Number with Alternating Bits
 * @Keyword: 2及以下为TRUE，幂次方或者幂次方+-1为true，向右移位1与上原数判断是不是幂次方-1
 * @Author: kami
 * @Date: 2022/1/3 11:13
 **/
func hasAlternatingBits(n int) bool {
	if n <= 2 {
		return true
	}
	if n&(n-1) == 0 || n&(n+1) == 0 {
		return false
	}
	m := n ^ (n >> 1)
	return m&(m+1) == 0
}

/**
 * @Description: 717. 1-bit and 2-bit Characters
 * @Keyword:  0 10 11
 * @Author: kami
 * @Date: 2022/1/3 12:04
 **/
func isOneBitCharacter(bits []int) bool {
	var ones int
	for i := len(bits) - 2; i >= 0 && bits[i] != 0; i-- {
		ones++
	}
	if ones%2 > 0 {
		return false
	}
	return true
}

/**
 * @Description: 724. Find Pivot Index
 * @Keyword: [1,7,3,6,5,6]
 * @Author: kami
 * @Date: 2022/1/4 22:18
 **/
func pivotIndex(nums []int) int {
	var sum int
	for i := 0; i < len(nums); i++ {
		sum += nums[i]
	}
	var preSum int
	for i := 0; i < len(nums); i++ {
		if preSum == sum-preSum-nums[i] {
			return i
		}
		preSum += nums[i]
	}
	return -1
}

/**
 * @Description: 728. Self Dividing Numbers
 * @Keyword: 一个数一个数字的判断，判断时获取最后一位数字
 * @Author: kami
 * @Date: 2022/1/4 22:31
 **/
func selfDividingNumbers(left int, right int) []int {
	var list []int
	for i := left; i <= right; i++ {
		var j = i
		for ; j > 0; i /= 10 {
			if j%10 == 0 || i%(j%10) != 0 {
				break
			}
		}
		if j == 0 {
			list = append(list, i)
		}
	}
	return list
}

/**
 * @Description: 733. Flood Fill
 * @Keyword: 递归
 * @Author: kami
 * @Date: 2022/1/4 22:42
 **/
func floodFill(image [][]int, sr int, sc int, newColor int) [][]int {
	var r, c = len(image), len(image[0])
	dfsFourDirection(image, sr, sc, r, c)
	for i := 0; i < r; i++ {
		for j := 0; j < c; j++ {
			if image[i][j] == -1 {
				image[i][j] = newColor
			}
		}
	}
	return image
}

func dfsFourDirection(image [][]int, r int, c int, h int, col int) {
	var temp = image[r][c]
	image[r][c] = -1
	// 上
	if r-1 >= 0 && image[r-1][c] == temp {
		dfsFourDirection(image, r-1, c, h, col)
	}
	// 下
	if r+1 < h && image[r+1][c] == temp {
		dfsFourDirection(image, r+1, c, h, col)
	}
	// 左
	if c-1 >= 0 && image[r][c-1] == temp {
		dfsFourDirection(image, r, c-1, h, col)
	}
	// 右
	if c+1 < col && image[r][c+1] == temp {
		dfsFourDirection(image, r, c+1, h, col)
	}
}

/**
 * @Description: 709. To Lower Case
 * @Keyword: 转为小写字母
 * @Author: kami
 * @Date: 2022/1/5 22:16
 **/
func toLowerCase(s string) string {
	var low []byte
	for i := 0; i < len(s); i++ {
		if s[i] >= 65 && s[i] <= 90 {
			low = append(low, s[i]+32)
		} else {
			low = append(low, s[i])
		}
	}
	return string(low)
}

/**
 * @Description: 744. Find Smallest Letter Greater Than Target
 * @Keyword: 找到最小的大于目标值
 * @Author: kami
 * @Date: 2022/1/5 22:22
 **/
func nextGreatestLetter(letters []byte, target byte) byte {
	var minGreater byte = 'z' + 1
	var min = letters[0]
	for i := 0; i < len(letters); i++ {
		if letters[i] > target && letters[i] < minGreater {
			minGreater = letters[i]
		}
		if letters[i] < min {
			min = letters[i]
		}
	}
	if minGreater == 'z'+1 {
		return min
	}
	return minGreater
}

/**
 * @Description: 747. Largest Number At Least Twice of Others
 * @Keyword:
 * @Author: kami
 * @Date: 2022/1/5 22:44
 **/
func dominantIndex(nums []int) int {
	var maxv, idx int
	for i, v := range nums {
		if maxv < v {
			maxv, idx = v, i
		}
	}

	for _, v := range nums {
		if v != maxv && v*2 > maxv {
			return -1
		}
	}

	return idx
}

/**
 * @Description: 748. Shortest Completing Word
 * @Keyword: 遍历
 * @Author: kami
 * @Date: 2022/1/6 8:27
 **/
func shortestCompletingWord(licensePlate string, words []string) string {
	primes := []int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
		47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101}
	product := 1
	product = productOfWord(licensePlate, product, primes)
	shortest, length := "", 16

	for _, word := range words {
		if productOfWord(word, 1, primes)%product == 0 && len(word) < length {
			shortest, length = word, len(word)
		}
	}
	return shortest
}

func productOfWord(s string, product int, primes []int) int {
	for _, i := range s {
		lowerIndex, higherIndex := i-'a', i-'A'
		if lowerIndex >= 0 && lowerIndex < 26 {
			product *= primes[lowerIndex]
		} else if higherIndex >= 0 && higherIndex < 26 {
			product *= primes[higherIndex]
		}
	}
	return product
}

/**
 * @Description: 762. Prime Number of Set Bits in Binary Representation
 * @Keyword: 两个步骤 1统计bit位 2判断bit位数量是质数
 * @Author: kami
 * @Date: 2022/1/6 21:26
 **/
func countPrimeSetBits(left int, right int) int {
	var cnt int
	for i := left; i <= right; i++ {
		if utils.IsPrime(utils.CountBit(i)) {
			cnt++
		}
	}
	return cnt
}

/**
 * @Description: 559. Maximum Depth of N-ary Tree
 * @Keyword: 统计N叉树的深度
 * @Author: kami
 * @Date: 2022/1/6 22:08
 **/
func maxDepth(root *leetcode.Node) int {
	if root == nil {
		return 0
	}
	return dfsDepth(root, 0)
}

func dfsDepth(cur *leetcode.Node, cnt int) int {
	cnt++
	size := len(cur.Children)
	if len(cur.Children) <= 0 {
		return cnt
	}
	var max int
	for i := 0; i < size; i++ {
		max = utils.GetMax(max, dfsDepth(cur.Children[i], cnt))
	}
	return max
}

/**
 * @Description: 590. N-ary Tree Postorder Traversal
 * @Keyword: 多叉树的后序遍历
 * @Author: kami
 * @Date: 2022/1/6 22:29
 **/
func postorder(root *leetcode.Node) []int {
	var res []int
	res = dfsPostOrder(root, res)
	return res
}

func dfsPostOrder(cur *leetcode.Node, res []int) []int {
	if cur == nil {
		return res
	}
	size := len(cur.Children)
	if size <= 0 {
		res = append(res, cur.Val)
		return res
	}

	for i := 0; i < size; i++ {
		res = dfsPostOrder(cur.Children[i], res)
	}
	res = append(res, cur.Val)
	return res
}

/**
 * @Description: 766. Toeplitz Matrix
 * @Keyword: 对角线数据相等，左边缘，上边缘为起点判断
 * @Author: kami
 * @Date: 2022/1/7 9:01
 **/
func isToeplitzMatrix(matrix [][]int) bool {
	if len(matrix) <= 1 || len(matrix[0]) == 1 {
		return true
	}
	// 第一列
	r := len(matrix)
	c := len(matrix[0])
	for i := 0; i < r; i++ {
		var curR = i + 1
		var curC = 1
		for curR < r && curC < c {
			if matrix[curR][curC] != matrix[i][0] {
				return false
			}
			curR++
			curC++
		}
	}
	for i := 0; i < c; i++ {
		var curR = 1
		var curC = i + 1
		for curR < r && curC < c {
			if matrix[curR][curC] != matrix[0][i] {
				return false
			}
			curR++
			curC++
		}
	}
	return true
}

/**
 * @Description: 700. Search in a Binary Search Tree
 * @Keyword: 二叉搜索树
 * @Author: kami
 * @Date: 2022/1/7 9:18
 **/
func searchBST(root *leetcode.TreeNode, val int) *leetcode.TreeNode {
	if root == nil {
		return nil
	}
	if root.Val == val {
		return root
	}
	if root.Val < val {
		return searchBST(root.Right, val)
	}

	return searchBST(root.Left, val)
}

/**
 * @Description: 703. Kth Largest Element in a Stream
 * @Keyword:
 * @Author: kami
 * @Date: 2022/1/7 9:23
 **/
type IntHeap []int

func (h IntHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h IntHeap) Len() int            { return len(h) }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
	x := (*h)[len(*h)-1]
	*h = (*h)[:len(*h)-1]
	return x
}

type KthLargest struct {
	h *IntHeap
	k int
}

func Constructor1(k int, nums []int) KthLargest {
	var ins KthLargest
	if len(nums) <= k {
		ins = KthLargest{h: (*IntHeap)(&nums), k: k}
		heap.Init(ins.h)
	} else {
		kNums := nums[:k]
		ins = KthLargest{h: (*IntHeap)(&kNums), k: k}
		heap.Init(ins.h)
		for i := k; i < len(nums); i++ {
			ins.Add(nums[i])
		}
	}
	return ins
}

func (this *KthLargest) Add(val int) int {
	if this.h.Len() < this.k {
		heap.Push(this.h, val)
	} else if val > (*this.h)[0] {
		(*this.h)[0] = val
		heap.Fix(this.h, 0)
	}
	return (*this.h)[0]
}

/**
 * @Description: 704. Binary Search
 * @Keyword: 二分查找
 * @Author: kami
 * @Date: 2022/1/9 22:45
 **/
func search(nums []int, target int) int {
	size := len(nums)
	if nums[0] > target || nums[size-1] < target {
		return -1
	}

	var left, right = 0, size
	for left <= right {
		var mid = (left + right) / 2
		switch {
		case nums[mid] == target:
			return mid
		case nums[mid] > target:
			right = mid - 1
		default:
			left = mid + 1
		}
	}
	return -1
}

/**
 * @Description: 783. Minimum Distance Between BST Nodes
 * @Keyword: 最接近的两个数的差
 * @Author: kami
 * @Date: 2022/1/9 22:54
 **/
func minDiffInBST(root *leetcode.TreeNode) int {
	min := math.MaxInt32
	prevVal := math.MinInt32
	helper := func(node *leetcode.TreeNode) {}
	helper = func(n *leetcode.TreeNode) {
		if n == nil {
			return
		}

		helper(n.Left)
		if prevVal != math.MinInt32 {
			d := n.Val - prevVal
			if d < min {
				min = d
			}
		}

		prevVal = n.Val
		helper(n.Right)
	}

	helper(root)

	return min
}

/**
 * @Description: 796. Rotate String
 * @Keyword: 移位比较
 * @Author: kami
 * @Date: 2022/1/11 21:37
 **/
func rotateString(s string, goal string) bool {
	if len(s) != len(goal) {
		return false
	}

	return strings.Contains(s+s, goal)
}

/**
 * @Description: 804. Unique Morse Code Words
 * @Keyword: 莫斯电码
 * @Author: kami
 * @Date: 2022/1/12 22:01
 **/
func uniqueMorseRepresentations(words []string) int {
	var cnt int
	mose := []string{".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."}
	moseMap := make(map[string]bool)
	for _, word := range words {
		var covertMose string
		for i := 0; i < len(word); i++ {
			covertMose += mose[word[i]-'a']
		}
		if !moseMap[covertMose] {
			cnt++
			moseMap[covertMose] = true
			continue
		}
	}
	return cnt
}

/**
 * @Description: 806. Number of Lines To Write String
 * @Keyword:
 * @Author: kami
 * @Date: 2022/1/15 12:41
 **/
func numberOfLines(widths []int, s string) []int {
	count := 0
	lineCount := 1
	for _, e := range s {
		if count+widths[e-'a'] <= 100 {
			count += widths[e-'a']
		} else {
			lineCount++
			count = widths[e-'a']
		}
	}
	return []int{lineCount, count}
}

/**
 * @Description: 812. Largest Triangle Area
 * @Keyword: 计算面积时需要直接使用常规的坐标三点平面三角计算公式,三个点如何选择，并没有太好的解决方案，用穷举法相对来说是一种可解的方案
 * @Author: kami
 * @Date: 2022/1/23 12:31
 **/
func largestTriangleArea(points [][]int) float64 {
	var res float64 = 0
	n := len(points)
	var x1, y1, x2, y2, x3, y3 int
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			for k := j + 1; k < n; k++ {
				x1 = points[i][0]
				x2 = points[j][0]
				x3 = points[k][0]
				y1 = points[i][1]
				y2 = points[j][1]
				y3 = points[k][1]
				res = math.Max(res, 0.5*math.Abs(float64(x1*y2+x2*y3+x3*y1-x2*y1-x3*y2-x1*y3)))
			}
		}
	}
	return res
}

/**
 * @Description: 819. Most Common Word
 * @Keyword: !?',;.
 * @Author: kami
 * @Date: 2022/1/24 21:27
 **/
func mostCommonWord(paragraph string, banned []string) string {
	m := make(map[string]int)
	m2 := make(map[string]int)
	s := ""
	max := 0
	res := ""

	for _, ban := range banned {
		m[ban] = 1
	}

	for _, i := range paragraph {
		if i == ' ' || i == ',' || i == '!' || i == '?' || i == '\'' || i == ';' || i == '.' {
			m2[s]++
			s = ""
		} else {
			s += strings.ToLower(string(i))
		}
	}
	m2[s]++

	for a, b := range m2 {
		if b > max && m[a] == 0 && a != "" {
			max = b
			res = a
		}
	}

	return res

}

/**
 * @Description: 821. Shortest Distance to a Character
 * @Keyword: 最近距离，左右开弓
 * @Author: kami
 * @Date: 2022/1/25 21:32
 **/
func shortestToChar(s string, c byte) []int {
	var size = len(s)
	var pos = -size
	var res []int
	for i := 0; i < size; i++ {
		if s[i] == c {
			pos = i
		}
		res = append(res, i-pos)
	}
	for i := pos - 1; i >= 0; i-- {
		if s[i] == c {
			pos = i
		}
		res[i] = utils.GetMin(res[i], pos-i)
	}

	return res
}

/**
 * @Description: 824. Goat Latin
 * @Keyword: 文字转换
 * @Author: kami
 * @Date: 2022/1/30 12:30
 **/
func toGoatLatin(sentence string) string {
	sp := strings.Split(sentence, " ")
	var res string
	// 3个规则 1/2互斥 3并列
	for i, curStr := range sp {
		var curRes string
		switch curStr[0] {
		case 'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U':
			curRes = curStr + "ma"
		default:
			size := len(curStr)
			if size > 1 {
				curRes = curStr[1:]
				curRes = curRes + string(curStr[0])
				curRes += "ma"
			} else {
				curRes = curStr + "ma"
			}
		}
		curIdx := i + 1
		var last string
		for idx := 0; idx < curIdx; idx++ {
			last += "a"
		}
		curRes += last

		res += " " + curRes
	}
	return res[1:]
}

/**
 * @Description: 830. Positions of Large Groups
 * @Keyword: 依次记录下标
 * @Author: kami
 * @Date: 2022/2/9 22:31
 **/
func largeGroupPositions(s string) [][]int {
	var startIdx int
	var cnt = 1
	size := len(s)
	var res [][]int
	for i := 1; i < size; i++ {
		if s[i] == s[i-1] {
			cnt++
			if i == size-1 && cnt > 2 {
				res = append(res, []int{startIdx, startIdx + cnt - 1})
			}
		} else {
			if cnt > 3 {
				res = append(res, []int{startIdx, startIdx + cnt - 1})
			}
			startIdx = i
			cnt = 1
		}
	}
	return res
}
